#leetcode题目169：多数元素
#难度：简单
#时间复杂度：O(n)
#空间复杂度：O(1)

#生活中也就是投票问题

#使用摩尔投票法 boyer-moore voting algorithm

from typing import List
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        """
        多数元素
        给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊n/2⌋ 的元素。
        你可以假设数组是非空的，并且给定的数组总是存在多数元素。
        
        使用摩尔投票法（Boyer-Moore Voting Algorithm）
        """
        num = nums[0]  # 候选元素
        count = 1      # 候选元素的计数
        
        for i in range(1, len(nums)):
            if count == 0:
                # 如果计数为0，选择当前元素作为新的候选元素
                num = nums[i]
                count += 1
            elif nums[i] == num:
                # 如果当前元素等于候选元素，计数加1
                count += 1
            else:
                # 如果当前元素不等于候选元素，计数减1
                count -= 1
        
        return num



#测试数据
nums = [3,2,3]
#预期输出：3
solution = Solution()
print(solution.majorityElement(nums))

nums = [2,2,1,1,1,2,2]
#预期输出：2
solution = Solution()
print(solution.majorityElement(nums))